package Binary_tree;

import java.util.HashMap;

public class Code06_PreAndInArrayToPosArray {
    public static void main(String[] args) {
        int[] pre = { 1, 2, 4, 5, 3, 6, 7 };
        int[] in = { 4, 2, 5, 1, 6, 3, 7 };
        int[] pos = getPostArray(pre, in);
        for (int i = 0; i != pos.length; i++) {
            System.out.print(pos[i] + " ");
        }
        System.out.println();
        //System.out.println(pos.toString());
        int[] pos2 = getPostArray(pre, in);
        for (int i = 0; i != pos2.length; i++) {
            System.out.print(pos2[i] + " ");
        }
        System.out.println();
    }

    public static int[] getPostArray(int[] pre, int[] in){
        if (pre == null || in == null || pre.length != in.length){
            return null;
        }
        int N = pre.length;
        int[] pos = new int[N];
        set(pre, in, pos, 0, N - 1, 0, N - 1, 0, N -1);
        return pos;
    }

    public static void set(int[] pre, int[] in, int[] pos,
                           int prei, int prej, int ini, int inj, int posi, int posj){
        if (prei > prej){ // 没有左子树
            return;
        }
        if (prei == prej){
            pos[posi] = pre[prei];
        }
        pos[posj] = pre[prei]; // 根填到后序最后
        // 找左树第一个节点
        int find = 0;
        for (; find < in.length; find++){
            if (in[find] == pre[prei]){
                break;
            }
        }
        // 填左树
        set(pre, in, pos, prei + 1, prei + find - ini, ini, find - 1, posi, posi + find - ini - 1);
        // 填右树
        set(pre, in, pos, prei + find - ini + 1, prej, find + 1, inj, posi + find - ini, posj - 1);
    }
    // 用HashMap减少遍历重复值
    public static int[] getPostArray2(int[] pre, int[] in){
        if (pre == null || in == null || pre.length != in.length){
            return null;
        }
        int N = pre.length;
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < N; i++) {
            map.put(in[i], i);
        }
        int[] pos = new int[N];
        set2(map, pre, in, pos, 0, N - 1, 0, N - 1, 0, N -1);
        return pos;
    }

    public static void set2(HashMap<Integer, Integer> map, int[] pre, int[] in, int[] pos,
                           int prei, int prej, int ini, int inj, int posi, int posj){
        if (prei > prej){ // 没有左子树
            return;
        }
        if (prei == prej){
            pos[posi] = pre[prei];
        }
        pos[posj] = pre[prei]; // 根填到后序最后
        // 找左树第一个节点
        int find = map.get(pre[prei]);
        // 填左树
        set2(map, pre, in, pos, prei + 1, prei + find - ini, ini, find - 1, posi, posi + find - ini - 1);
        // 填右树
        set2(map, pre, in, pos, prei + find - ini + 1, prej, find + 1, inj, posi + find - ini, posj - 1);

    }
}
